#Fat Chance: Modulos 1 e 2 - Contagem

Exercícios autopropostos para estudar técnicas de contagem e anaálise combinatória com dados do SGDC.

##Sequências

Sequencias são grupos de k objetos retirados de um grupo maior ou igual n. Para sequências a ordem em que são dispostos importa e podem ou não apresentar repetição.

###Sequências com repetição.

Uma notificação é um documento emitido pela Defesa Civil e identificado por um número sequêncial. Por um problema na gráfica que imprime as notificações da o lote de notificações que vão de 130.000 a 130.500 veio com os dois últimos dígitos apagados. Uma destas notificações foi emitida a um cidadão, que compareceu à CODESAL no dia seguinte portando o documento. O atendente identificou que tratava-se de uma notificação defeituosa, pois apresentava a numeração 130.4_ _. Considerando que os dois últimos digitos podem ser preenchidos com números de 0 a 9, com repetição (por exemplo, 130.499), quantas possibilidades temos para a numeração real desta notificação?

Para o primerio dígito temos as opções 0,1,2,3,4,5,6,7,8 e 9. Logo, n = 10. Para o segundo dígito, como são permitidas repetçãoes, temos as mesmas 10 opções.

Suponhamos que o primeiro dígito seja 1. Portanto, teremos as possibilidades de numeração:

for (i in seq(0,9,1)){
  print(paste0(130.41,i))
}
[1] "130.410"
[1] "130.411"
[1] "130.412"
[1] "130.413"
[1] "130.414"
[1] "130.415"
[1] "130.416"
[1] "130.417"
[1] "130.418"
[1] "130.419"

Da mesma forma, se tivéssemos certeza de que o segundo dígito faltante é o 2, teriamos as opções:

for (i in seq(0,9,1)){
  print(paste0(130.4,i,2))
}
[1] "130.402"
[1] "130.412"
[1] "130.422"
[1] "130.432"
[1] "130.442"
[1] "130.452"
[1] "130.462"
[1] "130.472"
[1] "130.482"
[1] "130.492"

Fixando o primeiro dígito faltante, teremos 10 possibilidades de numeração para cada uma das 10 opções. Podemos escrever todas as possibilidades

for (i in seq(0,9,1)){
  for (j in seq(0,9,1)) {
      print(paste0(130.4,i,j))
  }
}
[1] "130.400"
[1] "130.401"
[1] "130.402"
[1] "130.403"
[1] "130.404"
[1] "130.405"
[1] "130.406"
[1] "130.407"
[1] "130.408"
[1] "130.409"
[1] "130.410"
[1] "130.411"
[1] "130.412"
[1] "130.413"
[1] "130.414"
[1] "130.415"
[1] "130.416"
[1] "130.417"
[1] "130.418"
[1] "130.419"
[1] "130.420"
[1] "130.421"
[1] "130.422"
[1] "130.423"
[1] "130.424"
[1] "130.425"
[1] "130.426"
[1] "130.427"
[1] "130.428"
[1] "130.429"
[1] "130.430"
[1] "130.431"
[1] "130.432"
[1] "130.433"
[1] "130.434"
[1] "130.435"
[1] "130.436"
[1] "130.437"
[1] "130.438"
[1] "130.439"
[1] "130.440"
[1] "130.441"
[1] "130.442"
[1] "130.443"
[1] "130.444"
[1] "130.445"
[1] "130.446"
[1] "130.447"
[1] "130.448"
[1] "130.449"
[1] "130.450"
[1] "130.451"
[1] "130.452"
[1] "130.453"
[1] "130.454"
[1] "130.455"
[1] "130.456"
[1] "130.457"
[1] "130.458"
[1] "130.459"
[1] "130.460"
[1] "130.461"
[1] "130.462"
[1] "130.463"
[1] "130.464"
[1] "130.465"
[1] "130.466"
[1] "130.467"
[1] "130.468"
[1] "130.469"
[1] "130.470"
[1] "130.471"
[1] "130.472"
[1] "130.473"
[1] "130.474"
[1] "130.475"
[1] "130.476"
[1] "130.477"
[1] "130.478"
[1] "130.479"
[1] "130.480"
[1] "130.481"
[1] "130.482"
[1] "130.483"
[1] "130.484"
[1] "130.485"
[1] "130.486"
[1] "130.487"
[1] "130.488"
[1] "130.489"
[1] "130.490"
[1] "130.491"
[1] "130.492"
[1] "130.493"
[1] "130.494"
[1] "130.495"
[1] "130.496"
[1] "130.497"
[1] "130.498"
[1] "130.499"

Totalizando 100 possíveis numerações possíveis para a notificação defeituosa 130.4_ _ que chegou às mãos do atendente. Podemos, então, deduzir que o número de possibilidades, considerando que repetições são permitidas é igual ao número de opções (n) para o primeiro número vezes o número de opções para o segundo. Assim, se o n = 10, Podemos calcular facilmente o número de possibilidades para uma notificação que veio de um lote onde os três últimos dígitos vieram apagados:

130._ _ _ \(->(n . n . n) = n^3 = 10^3 = 1000\)

Ou seja, teríamos 1000 numerações possíveis.

Definição: O número de opções possíveis para uma sequência de \(k\) objetos retirados de \(n\) opções com repetições permitidas é \(n^k\).

###SequÊncias sem repetição.

Um enegnheiro recebe um conjunto com 10 ocorrências a serem atendidas ao longo do dia. Elas estão espalhadas pela cidade, então o engenheiro deve elaborar um roteiro que passe por todos os 10 pontos. Quantos roteiros diferentes podem ser montados?

De forma semelhante ao exemplo anterior, chamaremos de \(n\) o número de opções, ou, neste caso, o número de processos dentro do pacote, \(n = 10\)

Para a primeira parada do roteiro, temos 10 opções. Para segunda parada, teremos os 9 processos restantes, 8 para a terceira parada e assim sucessivamente. Pelo princípio da multiplicação, temos:

\(10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5\cdot4 \cdot 3 \cdot 2 \cdot 1 = 10! =3.628.800\)

Com apenas 10 processos temos mais de 3 milões e meio de roteiros possíveis!

LS0tDQp0aXRsZTogJ0ZhdCBDaGFuY2U6IENvdW50aW5nJw0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIGRmX3ByaW50OiBwYWdlZA0KLS0tDQpgYGB7ciwgZWNobyA9IEZBTFNFLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQ0KI0xvYWQgcGFja2FnZXMNCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkodGlkeXIpDQpsaWJyYXJ5KHRpYmJsZSkNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KGx1YnJpZGF0ZSkNCmxpYnJhcnkoem9vKQ0KbGlicmFyeShmb3JjYXRzKQ0KbGlicmFyeSh0aWR5dmVyc2UpDQpsaWJyYXJ5KGdnbWFwKQ0KbGlicmFyeShzZikNCmxpYnJhcnkoZ2lmc2tpKQ0KbGlicmFyeShvc21kYXRhKQ0KDQpgYGANCg0KI0ZhdCBDaGFuY2U6IE1vZHVsb3MgMSBlIDIgLSBDb250YWdlbQ0KDQpFeGVyY8OtY2lvcyBhdXRvcHJvcG9zdG9zIHBhcmEgZXN0dWRhciB0w6ljbmljYXMgZGUgY29udGFnZW0gZSBhbmHDoWxpc2UgY29tYmluYXTDs3JpYSBjb20gZGFkb3MgZG8gU0dEQy4gDQoNCiMjU2VxdcOqbmNpYXMNCg0KU2VxdWVuY2lhcyBzw6NvIGdydXBvcyBkZSBrIG9iamV0b3MgcmV0aXJhZG9zIGRlIHVtIGdydXBvIG1haW9yIG91IGlndWFsIG4uIFBhcmEgc2VxdcOqbmNpYXMgKiphIG9yZGVtIGVtIHF1ZSBzw6NvIGRpc3Bvc3RvcyBpbXBvcnRhKiogZSBwb2RlbSBvdSBuw6NvIGFwcmVzZW50YXIgcmVwZXRpw6fDo28uIA0KDQojIyNTZXF1w6puY2lhcyBjb20gcmVwZXRpw6fDo28uIA0KDQpVbWEgbm90aWZpY2HDp8OjbyDDqSB1bSBkb2N1bWVudG8gZW1pdGlkbyBwZWxhIERlZmVzYSBDaXZpbCBlIGlkZW50aWZpY2FkbyBwb3IgdW0gbsO6bWVybyBzZXF1w6puY2lhbC4gUG9yIHVtIHByb2JsZW1hIG5hIGdyw6FmaWNhIHF1ZSBpbXByaW1lIGFzIG5vdGlmaWNhw6fDtWVzIGRhIG8gbG90ZSBkZSBub3RpZmljYcOnw7VlcyBxdWUgdsOjbyBkZSAxMzAuMDAwIGEgMTMwLjUwMCB2ZWlvIGNvbSBvcyBkb2lzIMO6bHRpbW9zIGTDrWdpdG9zIGFwYWdhZG9zLiBVbWEgZGVzdGFzIG5vdGlmaWNhw6fDtWVzIGZvaSBlbWl0aWRhIGEgdW0gY2lkYWTDo28sIHF1ZSBjb21wYXJlY2V1IMOgIENPREVTQUwgbm8gZGlhIHNlZ3VpbnRlIHBvcnRhbmRvIG8gZG9jdW1lbnRvLiANCk8gYXRlbmRlbnRlIGlkZW50aWZpY291IHF1ZSB0cmF0YXZhLXNlIGRlIHVtYSBub3RpZmljYcOnw6NvIGRlZmVpdHVvc2EsIHBvaXMgYXByZXNlbnRhdmEgYSBudW1lcmHDp8OjbyAxMzAuNF8gXy4gDQpDb25zaWRlcmFuZG8gcXVlIG9zIGRvaXMgw7psdGltb3MgZGlnaXRvcyBwb2RlbSBzZXIgcHJlZW5jaGlkb3MgY29tIG7Dum1lcm9zIGRlIDAgYSA5LCBjb20gcmVwZXRpw6fDo28gKHBvciBleGVtcGxvLCAxMzAuNDk5KSwgcXVhbnRhcyBwb3NzaWJpbGlkYWRlcyB0ZW1vcyBwYXJhIGEgbnVtZXJhw6fDo28gcmVhbCBkZXN0YSBub3RpZmljYcOnw6NvPyANCg0KUGFyYSBvIHByaW1lcmlvIGTDrWdpdG8gdGVtb3MgYXMgb3DDp8O1ZXMgMCwxLDIsMyw0LDUsNiw3LDggZSA5LiBMb2dvLCBuID0gMTAuIA0KUGFyYSBvIHNlZ3VuZG8gZMOtZ2l0bywgY29tbyBzw6NvIHBlcm1pdGlkYXMgcmVwZXTDp8Ojb2VzLCB0ZW1vcyBhcyBtZXNtYXMgMTAgb3DDp8O1ZXMuIA0KDQpTdXBvbmhhbW9zIHF1ZSBvIHByaW1laXJvIGTDrWdpdG8gc2VqYSAxLiBQb3J0YW50bywgdGVyZW1vcyBhcyBwb3NzaWJpbGlkYWRlcyBkZSBudW1lcmHDp8OjbzoNCg0KYGBge3J9DQpmb3IgKGkgaW4gc2VxKDAsOSwxKSl7DQogIHByaW50KHBhc3RlMCgxMzAuNDEsaSkpDQp9DQpgYGANCkRhIG1lc21hIGZvcm1hLCBzZSB0aXbDqXNzZW1vcyBjZXJ0ZXphIGRlIHF1ZSBvIHNlZ3VuZG8gZMOtZ2l0byBmYWx0YW50ZSDDqSBvIDIsIHRlcmlhbW9zIGFzIG9ww6fDtWVzOiANCg0KYGBge3J9DQpmb3IgKGkgaW4gc2VxKDAsOSwxKSl7DQogIHByaW50KHBhc3RlMCgxMzAuNCxpLDIpKQ0KfQ0KYGBgDQoNCkZpeGFuZG8gbyBwcmltZWlybyBkw61naXRvIGZhbHRhbnRlLCB0ZXJlbW9zIDEwIHBvc3NpYmlsaWRhZGVzIGRlIG51bWVyYcOnw6NvIHBhcmEgY2FkYSB1bWEgZGFzIDEwIG9ww6fDtWVzLiBQb2RlbW9zIGVzY3JldmVyIHRvZGFzIGFzIHBvc3NpYmlsaWRhZGVzIA0KDQpgYGB7cn0NCmZvciAoaSBpbiBzZXEoMCw5LDEpKXsNCiAgZm9yIChqIGluIHNlcSgwLDksMSkpIHsNCiAgICAgIHByaW50KHBhc3RlMCgxMzAuNCxpLGopKQ0KICB9DQp9DQpgYGANCg0KVG90YWxpemFuZG8gMTAwIHBvc3PDrXZlaXMgbnVtZXJhw6fDtWVzIHBvc3PDrXZlaXMgcGFyYSBhIG5vdGlmaWNhw6fDo28gZGVmZWl0dW9zYSAxMzAuNF8gXyBxdWUgY2hlZ291IMOgcyBtw6NvcyBkbyBhdGVuZGVudGUuIFBvZGVtb3MsIGVudMOjbywgZGVkdXppciBxdWUgbyBuw7ptZXJvIGRlIHBvc3NpYmlsaWRhZGVzLCBjb25zaWRlcmFuZG8gcXVlIHJlcGV0acOnw7VlcyBzw6NvIHBlcm1pdGlkYXMgw6kgaWd1YWwgYW8gbsO6bWVybyBkZSBvcMOnw7VlcyAobikgcGFyYSBvIHByaW1laXJvIG7Dum1lcm8gdmV6ZXMgbyBuw7ptZXJvIGRlIG9ww6fDtWVzIHBhcmEgbyBzZWd1bmRvLiBBc3NpbSwgc2UgbyBuID0gMTAsIFBvZGVtb3MgY2FsY3VsYXIgZmFjaWxtZW50ZSBvIG7Dum1lcm8gZGUgcG9zc2liaWxpZGFkZXMgcGFyYSB1bWEgbm90aWZpY2HDp8OjbyBxdWUgdmVpbyBkZSB1bSBsb3RlIG9uZGUgb3MgdHLDqnMgw7psdGltb3MgZMOtZ2l0b3MgdmllcmFtIGFwYWdhZG9zOg0KDQoxMzAuXyBfIF8gJC0+KG4gIC4gbiAuIG4pID0gbl4zID0gMTBeMyA9IDEwMDAkIA0KDQpPdSBzZWphLCB0ZXLDrWFtb3MgMTAwMCBudW1lcmHDp8O1ZXMgcG9zc8OtdmVpcy4gDQoNCioqRGVmaW5pw6fDo286KiogTyBuw7ptZXJvIGRlIG9ww6fDtWVzIHBvc3PDrXZlaXMgcGFyYSB1bWEgc2VxdcOqbmNpYSBkZSAkayQgb2JqZXRvcyByZXRpcmFkb3MgZGUgJG4kIG9ww6fDtWVzICoqY29tIHJlcGV0acOnw7VlcyBwZXJtaXRpZGFzKiogw6kgJG5eayQuICANCg0KIyMjU2VxdcOKbmNpYXMgc2VtIHJlcGV0acOnw6NvLiANCg0KVW0gZW5lZ25oZWlybyByZWNlYmUgdW0gY29uanVudG8gY29tIDEwIG9jb3Jyw6puY2lhcyBhIHNlcmVtIGF0ZW5kaWRhcyBhbyBsb25nbyBkbyBkaWEuIEVsYXMgZXN0w6NvIGVzcGFsaGFkYXMgcGVsYSBjaWRhZGUsIGVudMOjbyBvIGVuZ2VuaGVpcm8gZGV2ZSBlbGFib3JhciB1bSByb3RlaXJvIHF1ZSBwYXNzZSBwb3IgdG9kb3Mgb3MgMTAgcG9udG9zLiBRdWFudG9zIHJvdGVpcm9zIGRpZmVyZW50ZXMgcG9kZW0gc2VyIG1vbnRhZG9zPyANCg0KYGBgIHtSfQ0KcGRhdGE8LSByZWFkLmNzdigic2dkY19hbm9tLmNzdiIsIHNlcCA9ICIsIikNCg0KcGFjb3RlIDwtIHBkYXRhICU+JSBmaWx0ZXIoeWVhcihkYXRhX3NvbGljKSA9PSAyMDE5LG9jb3JyX3NvbGljID09ICJERVNMSVpBTUVOVE8gREUgVEVSUkEiKSAlPiUgDQogICAgICAgICAgICAgICAgICAgIHNlbGVjdChjb2RfcHJvYyxub21lX2JhaXJybyxjb29yZF94aV9sb2dyYSwgY29vcmRfeWlfbG9ncmEpICU+JSANCiAgICAgICAgICAgICAgICAgICAgc2FtcGxlX24oMTApDQpwYWNvdGUgIA0KYGBgDQoNCkRlIGZvcm1hIHNlbWVsaGFudGUgYW8gZXhlbXBsbyBhbnRlcmlvciwgY2hhbWFyZW1vcyBkZSAkbiQgbyBuw7ptZXJvIGRlIG9ww6fDtWVzLCBvdSwgbmVzdGUgY2FzbywgbyBuw7ptZXJvIGRlIHByb2Nlc3NvcyBkZW50cm8gZG8gcGFjb3RlLCAkbiA9IDEwJA0KDQpQYXJhIGEgcHJpbWVpcmEgcGFyYWRhIGRvIHJvdGVpcm8sIHRlbW9zIDEwIG9ww6fDtWVzLiBQYXJhIHNlZ3VuZGEgcGFyYWRhLCB0ZXJlbW9zIG9zIDkgcHJvY2Vzc29zIHJlc3RhbnRlcywgOCBwYXJhIGEgdGVyY2VpcmEgcGFyYWRhIGUgYXNzaW0gc3VjZXNzaXZhbWVudGUuIFBlbG8gcHJpbmPDrXBpbyBkYSBtdWx0aXBsaWNhw6fDo28sIHRlbW9zOg0KDQokMTAgXGNkb3QgOSBcY2RvdCA4IFxjZG90IDcgXGNkb3QgNiBcY2RvdCA1XGNkb3Q0IFxjZG90IDMgXGNkb3QgMiBcY2RvdCAxID0gMTAhID0zLjYyOC44MDAkDQoNCkNvbSBhcGVuYXMgMTAgcHJvY2Vzc29zIHRlbW9zIG1haXMgZGUgMyBtaWzDtWVzIGUgbWVpbyBkZSByb3RlaXJvcyBwb3Nzw612ZWlzISANCg0KYGBge3J9DQptYWRfbWFwIDwtIGdldF9tYXAoYygtMzguNTUsLTEzLjAyNSwtMzguMywtMTIuODUpLCBtYXB0eXBlID0gInRlcnJhaW4iKQ0KYGBgDQpgYGB7ciwgYW5pbWF0aW9uLmhvb2s9J2dpZnNraScsIGVjaG89RkFMU0UsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIGZpZy5hbGlnbiA9ICdjZW50ZXInfQ0KZm9yIChpIGluIHNlcSgxLDEwLDEpKSB7DQogIHBhY290ZSA8LSBwYWNvdGVbc2FtcGxlKG5yb3cocGFjb3RlKSksXQ0KICBwbG90MSA8LSBnZ21hcChtYWRfbWFwKSsNCiAgZ2VvbV9wb2ludChkYXRhID0gcGFjb3RlLCBhZXMoeD1hcy5udW1lcmljKGNvb3JkX3hpX2xvZ3JhKSwgeSA9IGFzLm51bWVyaWMoY29vcmRfeWlfbG9ncmEpKSxzaGFwZT0xOSwgc2l6ZSA9IDMsIGNvbG9yID0icmVkIikrDQogIGdlb21fcGF0aChkYXRhPSBwYWNvdGUsIGFlcyh4PWFzLm51bWVyaWMoY29vcmRfeGlfbG9ncmEpLCB5ID0gYXMubnVtZXJpYyhjb29yZF95aV9sb2dyYSkpKQ0KICBwcmludChwbG90MSkNCn0NCmBgYA0KDQoNCg0KDQo=